#include<bits/stdc++.h>
using namespace std;

typedef struct node {
    int elem;
    struct node *next;
} sNode, *sListPtr;

// 初始化链表，分配头节点内存
/**
 * @param &L this link
 * @return 是否创建成功
 */
bool initList(sListPtr &L) {
    
    L = (sNode*)malloc(sizeof(sNode));

    if (L != NULL) {
        cout << "创建成功！" << endl;
        L->next = NULL;
        return true;
    }

    else {
        cout << "创建失败！" << endl;
        return false;
    }
}

// 按位序插入元素到链表中
bool rankInsert(sListPtr &L, int i, int e) {
    // 按位序插入
    if (i < 1) {
        cout << "位序不合法！" << endl;
        return false;
    }
    sNode *p = L;
    int j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        cout << "空间不足！" << endl;
        return false;
    }
    sNode *s = (sNode*)malloc(sizeof(sNode));
    s->elem = e;
    s->next = p->next;
    p->next = s;
    cout << "元素插入成功！" << endl;
    return true;
}

// 在指定节点后插入元素
bool postInsert(sNode *p, int e) {
    sNode *s = (sNode*)malloc(sizeof(sNode));
    s->elem = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 在指定节点前插入元素
bool preInsert(sNode *p, int e) {
    sNode *s = (sNode*)malloc(sizeof(sNode));
    s->next = p->next;
    p->next = s;
    s->elem = p->elem;
    p->elem = e;
    return true;
}

// 按位序删除链表中的元素
bool rankDel(sListPtr &L, int i) {
    if (i < 1) {
        cout << "位序不合法！" << endl;
        return false;
    }
    sNode *p = L;
    int j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL) {
        cout << "空间不足或位序不合法！" << endl;
        return false;
    }
    sNode *tmp = p->next;
    p->next = tmp->next;
    free(tmp);
    cout << "删除成功！" << endl;
    return true;
}

// 删除指定节点的下一个节点
bool delP(sNode *p) {
    if (p == NULL || p->next == NULL) {
        cout << "删除失败！" << endl;
        return false;
    }
    sNode *tmp = p->next;
    p->next = tmp->next;
    free(tmp);
    return true;
}

// 正向建立链表
sListPtr fowardCreat(sListPtr &L) {
    // 正向建立
    int x;
    L = (sNode*)malloc(sizeof(sNode));
    L->next = NULL; // 初始化头节点的next指针为NULL
    sNode *s, *r = L; // r指向头节点
    while (cin >> x && x != 9999) {
        s = (sNode*)malloc(sizeof(sNode));
        s->elem = x;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return L;
}

// 打印链表中所有节点的值
void printList(sListPtr L) {
    sNode *p = L->next;
    int i = 1;
    while (p != NULL) {
        cout << "节点" << i << "值为：" << p->elem << endl;
        p = p->next;
        i++;
    }
}

// 按值查找操作函数
sNode* findByValue(sListPtr L, int value,int &pos) {
    sNode *p = L->next;
    pos=1;
    while (p != NULL) {
        if (p->elem == value) {
            return p;
        }
        p = p->next;
        pos++;
    }
    return NULL;
}

// 按位序查找操作函数
sNode* findByPosition(sListPtr L, int position) {
    if (position < 1) {
        cout << "位序不合法！" << endl;
        return NULL;
    }
    sNode *p = L->next;
    int j = 1;
    while (p != NULL && j < position) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        cout << "位序超出范围！" << endl;
        return NULL;
    }
    return p;
}



// 主函数，演示链表的初始化、创建、插入、删除和查找操作
int main() {
    sListPtr L;
    initList(L); // 初始化链表

    cout << "输入链表元素（输入9999结束）：" << endl;
    fowardCreat(L); // 正向建立链表
    printList(L);

    int i, e;
    cout << "输入要插入的值：";
    cin >> e;
    cout << "输入要插入到哪个节点之前（位序）：";
    cin >> i;

    // 找到第 i 个节点
    sNode *p = findByPosition(L, i);
    if (p != NULL) {
        if (preInsert(p, e)) {
            cout << "元素插入成功！" << endl;
            printList(L);
        } else {
            cout << "插入失败！" << endl;
        }
    } else {
        cout << "未找到位序为 " << i << " 的节点！" << endl;
    }

    cout << "输入要查找的值：";
    cin >> e;
    int ind = 1;
    sNode *foundNodeValue = findByValue(L, e, ind);
    if (foundNodeValue != NULL) {
        cout << "找到值为 " << e << " 的节点！" << endl;
        cout << "位序是：" << ind << endl;
    } else {
        cout << "未找到值为 " << e << " 的节点！" << endl;
    }

    cout << "输入要查找的位序：";
    cin >> i;
    sNode *foundNodePosition = findByPosition(L, i);
    if (foundNodePosition != NULL) {
        cout << "找到位序为 " << i << " 的节点，其值为：" << foundNodePosition->elem << endl;
    } else {
        cout << "未找到位序为 " << i << " 的节点！" << endl;
    }

    cout << "输入要删除哪个节点的下一个节点？";
    cin >> i;
    sNode *pDel = L->next;
    int j = 0;
    while (pDel != NULL && j < i - 1) {
        pDel = pDel->next;
        j++;
    }
    if (pDel != NULL && pDel->next != NULL) {
        delP(pDel);
        cout << "当前的表中是：" << endl;
        printList(L);
    } else {
        cout << "指定的节点或其下一个节点不存在！" << endl;
    }

    return 0;
}

// slist head_insert(slist &L){
//     node* s;
//     int x;
//     L->next=NULL;
//     cin>>x;
//     while(x!=114514){
//         s=new node;
//         s->data=x;
//         s->next=L->next;
//         L->next=s;
//         cin>>x;
//     }
   
//     return L;
// }